package com.jerry.hm.datastructure.stack;

import java.util.Stack;

/**
 * 中缀表达式转后缀
 *
 * @author Jerry
 * @since 2024/10/4 9:51
 */
public class InfixToSuffix {

    public static String infixToSuffix(String exp) {
        Stack<Character> stack = new Stack<>();
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < exp.length(); i++) {
            char c = exp.charAt(i);
            switch (c) {
                case '+', '-', '*', '/' -> {
                    if (stack.isEmpty()) {
                        stack.push(c);
                    } else {
                        while (!stack.isEmpty() && priority(stack.peek()) >= priority(c)) {
                            sb.append(stack.pop());
                        }
                        stack.push(c);
                    }
                }
                case '(' -> stack.push(c);
                case ')' -> {
                    while (!stack.isEmpty() && stack.peek() != '(') {
                        sb.append(stack.pop());
                    }
                    stack.pop();
                }
                default -> sb.append(c);
            }
        }

        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }


        return sb.toString();
    }

    /**
     * 判断运算符的优先级
     *
     * @param op
     * @return
     */
    private static int priority(char op) {
        return switch (op) {
            case '*', '/' -> 2;
            case '+', '-' -> 1;
            case '(', ')' -> 0;
            default -> throw new IllegalArgumentException("不合法的运算符" + op);
        };
    }
}
